//
// Created by user on 2022/1/17.
//
#include <iostream>
#include <vector>
using namespace std;
void myswap(vector<int> &nums, int start, int end);
void rotate(vector<int>& nums, int k) {
    int n = nums.size();

    vector<int> newNums(n, 0);
    for (int i=0; i<n; i++){
        int index = (i+k)%n;
        newNums[index] = nums[i];
    }

    nums.assign(newNums.begin(), newNums.end());
}

//// 方案二：环状替换
void rotate1(vector<int>& nums, int k) {
    int n = nums.size();
    k = k%n;
    int count = 0;
    for(int start = 0; count<n; start++){
        int current = start;
        int prev = nums[start];

        do {
            int next = (current+k)%n;
            int tmp = nums[next];
            nums[next] = prev;
            prev=tmp;
            current = next;
            count++;
        }while (start!=current);
    }

}
// 方案三：数组旋转
void rotate2(vector<int>& nums, int k) {
    int n = nums.size();
    k = k%n;
    myswap(nums, 0, n-1);
    myswap(nums, 0, k-1);
    myswap(nums, k, n-1);

}

void myswap(vector<int> &nums, int start, int end){
    while (start<end){
        int tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
        start++;
        end--;
    }
}

